#include <iostream>
#include <vector>

using namespace std;

class Point
{
public:
	double x;
	double y;

	Point()
	{
		this->x = 0.0;
		this->y = 0.0;
	}

	Point(double x, double y)
	{
		this->x = x;
		this->y = y;
	}
};

class WeightPoint : public Point
{
public:
	double weight;

	WeightPoint() : Point()
	{
		weight = 0.0;
	}

	WeightPoint(Point pt, double weight) : Point(pt)
	{
		this->weight = weight;
	}
};

double EuclideanDistance(const Point & a,const Point & b)
{
	return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

int getclosestCenter(const vector<Point> & centers, const Point & pt)
{
	vector<double> distances(centers.size());
	for(int i = 0; i < centers.size(); ++i)
	{
		distances[i] = EuclideanDistance(centers[i], pt);
	}

	int result = 0;
	double minDistance = distances[0];

	for(int i = 1; i < distances.size(); ++i)
	{
		if(distances[i] < minDistance)
		{
			minDistance = distances[i];
			result = i;
		}
	}
	return result;
}

Point calcNewCenter(const vector<int> & clusters, int centerNumber, const vector<WeightPoint> & points)
{
	Point result, tempS;
	double fullWeight = 0;
	for(int i = 0; i < clusters.size(); i++)
	{
		if(clusters[i] == centerNumber)
		{
			tempS.x += points[i].x * points[i].weight;
			tempS.y += points[i].y * points[i].weight;
			fullWeight += points[i].weight;
		}
	}
	result.x = tempS.x / fullWeight;
	result.y = tempS.y / fullWeight;
	return result;
}

int main()
{
	int n = 6; //number of points
	int k = 3; //number of clusters

	vector<WeightPoint> points(n);
	points[0] = WeightPoint(Point(3, 3), 5);
	points[1] = WeightPoint(Point(2, 8), 2);
	points[2] = WeightPoint(Point(4, 6), 1);
	points[3] = WeightPoint(Point(5, 10), 2);
	points[4] = WeightPoint(Point(7, 5), 3);
	points[5] = WeightPoint(Point(7, 8), 3);

	vector<Point> centers(k);
	centers[0] = Point(4, 5);
	centers[1] = Point(5, 5);
	centers[2] = Point(6, 8);

	vector<int> clusters(n);

	bool isClusterChanged = true;
	int tempCenter;

	while(isClusterChanged == true)
	{
		isClusterChanged = false;

		//creating cluster
		for(int i = 0; i < points.size(); ++i)
		{
			tempCenter = getclosestCenter(centers, points[i]);
			if(tempCenter != clusters[i])
			{
				clusters[i] = tempCenter;
				isClusterChanged = true;
			}
		}

		//calculating new center
		for(int i = 0; i < centers.size(); i++)
		{
			centers[i] = calcNewCenter(clusters, i, points);
		}
	}

	for(int i = 0; i < centers.size(); ++i)
	{
		cout << centers[i].x << " " << centers[i].y << endl;
		for(int j = 0; j < clusters.size(); ++j)
		{
			if(clusters[j] == i)
			{
				cout << points[j].x << " " << points[j].y << endl;
			}
		}
		cout << endl;
	}
	return 0;
}